package com.leetcode.string;

/**
 * 5. 最长回文子串
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * 示例 1：
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * 示例 2：
 * 输入：s = "cbbd"
 * 输出："bb"
 * 示例 3：
 * 输入：s = "a"
 * 输出："a"
 * 示例 4：
 * 输入：s = "ac"
 * 输出："a"
 * 提示：
 * 1 <= s.length <= 1000
 * s 仅由数字和英文字母（大写和/或小写）组成
 */
class Code05 {
    public static void main(String[] args) {
        Code05 code09 = new Code05();
        String s = "cbbd";
        String s1 = code09.longestPalindrome2(s);
        System.out.println(s1);
    }

    /**
     * 动态规划求解
     * 对于一个子串而言，如果它是回文串，并且长度大于 22，那么将它首尾的两个字母去除之后，它仍然是个回文串。
     * 例如对于字符串“ababa”，如果我们已经知道 "bab” 是回文串，那么“ababa” 一定是回文串，这是因为它的首尾两个字母都是“a”。
     * 根据这样的思路，我们就可以用动态规划的方法解决本题
     * 动态规划方程：P(i,j)=P(i+1,j−1)∧(Si==Sj)
     * 也就是说，只有 s[i+1:j-1]是回文串，并且 s 的第 i 和 j 个字母相同时，s[i:j]才会是回文串
     * @param s
     * @return
     */
    public String longestPalindrome2(String s) {
        if(s.length() <= 1){
            return s;
        }
        if(s.length() == 2 && s.charAt(0) == s.charAt(1)){
            return s;
        }
        int maxLen = 1;
        int startIndex = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[s.length()][s.length()];
        // 初始化：所有长度为 1 的子串都是回文串
        for(int i = 0;i<s.length();i++){
            dp[i][i] = true;
        }
        // 递推开始
        // 先枚举子串长度
        for(int len = 2;len<=s.length();len++){
            // 枚举左边界，左边界的上限设置可以宽松一些
            for(int i = 0;i<s.length();i++){
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = len + i -1;
                // 如果右边界越界，就可以退出当前循环
                if(j >= s.length()){
                    break;
                }
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = len < 3 ? true : dp[i+1][j-1];
                }else {
                    dp[i][j] = false;
                }
                if(dp[i][j] && j-i+1 > maxLen){
                    maxLen = j-i+1;
                    startIndex = i;
                }
            }
        }
        return s.substring(startIndex,startIndex+maxLen);
    }

    /**
     * 暴力求解-超时
     * @param s
     * @return
     */
    public String longestPalindrome1(String s) {
        String str = "";
        int len = -1;
        for(int i=0;i<s.length();i++){
            for(int j=i;j<=s.length();j++){
                if(check(s.substring(i,j))){
                    if(s.substring(i,j).length() > len){
                        len = s.substring(i,j).length();
                        str = s.substring(i,j);
                    }
                }
            }
        }
        return str;
    }

    private boolean check(String s){
        char[] chars = s.toCharArray();
        int p = 0;
        int q = chars.length-1;
        while (p<q){
            if(chars[p] != chars[q]){
                return false;
            }
            p++;
            q--;
        }
        return true;
    }

}
